package com.kevinkk.array;

/**
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 *
 * 本质上还是二分查找，target是 x，数组的元素是从0 到 x
 * 但是需要留意的是 long res = (long)mid * mid; 这一步需要用 long 来存储
 * 最后由于只保留整数部分，也就是第一个比 target 小的元素，因此是 right指针
 */

public class Sqrtx {
    public int mySqrt(int x) {
        int left = 0, right = x;
        int mid = 0;
        while(left <= right){
            mid = (left +right) / 2;
            // 需要注意的是 mid * mid 的时候就已经有可能发生溢出了，因此在右边也需要进行类型转换
            long res = (long)mid * mid;
            if(res == x){
                return mid;
            }else if(res < x){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        return right;
    }
}
